package main

import (
	"container/list"
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//使用golang的list作为队列
func levelOrder1(root *TreeNode) (res []int) {
	if root == nil {
		return
	}
	queue := list.New()
	queue.PushBack(root)
	for queue.Len() > 0 {
		//先进先出
		node := queue.Remove(queue.Front()).(*TreeNode) //弹出队列第一个元素并进行断言
		if node.Left != nil {
			queue.PushBack(node.Left)
		}
		if node.Right != nil {
			queue.PushBack(node.Right)
		}
		res = append(res, node.Val)
	}
	return res
}

//自己写个数组作为队列 先进先出
func levelOrder2(root *TreeNode) []int {
	var (
		res []int       //用于存放结果
		ts  []*TreeNode //将树依次输入到这个切片中 作为队列 先进先出
		n   int
	)

	ts = []*TreeNode{root}
	for n < len(ts) { //遍历完ts中所有元素
		v := ts[n]    //存放此次循环遍历到的树节点
		ts[n] = nil   //模拟出队 没有该句也无妨
		if v != nil { //如果不为空
			res = append(res, v.Val)
		} else {
			continue //如果为空 继续下去
		}
		if v.Left != nil {
			ts = append(ts, v.Left) //添加左子树进ts
		}
		if v.Right != nil {
			ts = append(ts, v.Right) //添加右子树进ts
		}
		n++
	}
	return res
}

func main() {
	t := &TreeNode{Val: 1}
	t.Left = &TreeNode{Val: 2}
	t.Right = &TreeNode{Val: 3}
	t.Left.Left = &TreeNode{Val: 4}
	t.Left.Right = &TreeNode{Val: 5}
	t.Right.Left = &TreeNode{Val: 6}
	/*树的形状
	       1
	    /     \
	   2       3
	  / \     /
	 4   5   6             */
	fmt.Println("层次排序:")
	fmt.Println(levelOrder1(t))

}
